package map;


//表示树的一个节点
class Node{

    public int key;
    Node left = null;
    Node right = null;

    public Node(int key) {
        this.key = key;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}
public class BinarySearchTree {
    //表示当前树的根节点
    private Node root = null;

    //把新的元素插入到树中
    public void insert(int key){
        Node newNode = new Node(key);
        //如果当前树是空树的话，就直接用root指向新节点即可
        if(root == null){
            root = newNode;
            return;
        }
        //如果是普通的树的话，就需要找到要插入的位置，再进行插入，
        //cur用来找待插入元素的位置
        //parent 记录 cur 的父元素
        Node cur = root;
        Node parent = null;
        while(cur != null){
            if(key < cur.key){
                //比根节点的元素小，就往左找
                parent = cur;
                cur = cur.left;

            }else if(key > cur.key){
                //比根节点的元素大，就往右找
                parent = cur;
                cur = cur.right;
            }else{
                //对于相同的情况，其实是存在许多不同的处理方式
                //我们这里是不允许重复的key出现的，这里就直接return即可
                return;
            }
        }

        //这个while循环走完以后，我们就得到了cur为null的情况,此时parent就是要插入元素的父节点
        //这就需要把newNode插入到parent的子节点上
        //这时候还要再判断一次新节点是插到parent的左子树，还是右子树上
        if(key < parent.key){
            parent.left = newNode;
        }else{
            parent.right = newNode;
        }
    }

    public static void preOrder(Node root){
        if(root == null){
            return;
        }
        System.out.print(root.key + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void inOrder(Node root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.key + " ");
        inOrder(root.right);
    }

    public void print(){
        System.out.println("前序遍历：");
        preOrder(root);
        System.out.println();
        System.out.println("中序遍历：");
        inOrder(root);
    }

    public Node find(int key){
        if(root == null){
            return null;
        }
        Node cur = root;
        while(cur != null){
            if(key < cur.key){
                cur = cur.left;
            }else if(key > cur.key){
                cur = cur.right;
            }else{
                //相等，找到了
                return cur;
            }
        }
        //如果while循环完都没有找到，那么就没有查找到,说明不存在
        return null;
    }

    public void remove(int key){
        if(root == null){
            return;
        }
        Node cur = root;
        Node parent = null;
        while(cur != null){
            if(key > cur.key){
                //比根节点的值大，就去根节点的右面找
                parent = cur;//更新父节点的位置
                cur = cur.right;
            }else if(key < cur.key){
                parent = cur;
                cur = cur.left;
            }else{
                //相等，直接进行删除操作即可
                removeNode(parent,cur);
                return;
            }
        }
    }

    public void removeNode(Node parent,Node cur){
        //共分为4大种情况
        //1,cur没有子树
        if(cur.right == null && cur.left == null){
            //1.1,如果cur就是root，就需要对root进行调整
            if(cur == root){
                //这时候整个树只有一个root节点，把root删除后，相当于树就成了空树
                root = null;
                return;
            }

            //1.2  cur不是root，同时cur是parent的左子树
             if(cur == parent.left){
                 //这时候直接删除cur即可
                parent.left = null;
                return;
            }

             //1.3 cur不是root,同时是parent的右子树
            if(cur == parent.right){
                parent.right = null;
                return;
            }
            //这里我们最后还是加个return，虽然理论上来说是不会走到这里的，但是为了稳妥还是加个。
            return;
        }

        //2.cur只有左子树
        if(cur.left != null && cur.right == null){
            //2.1 cur为root
            if(cur == root){
                //cur的左子树的第一个节点就变成了根节点了
                root = cur.left;
                return;
            }

            //2.2  cur不是root，同时cur是parent的左子树
            if(cur == parent.left){
                parent.left = cur.left;
                return;
            }

            //2.3  cur不是root，同时cur是parent的右子树
            if(cur == parent.right){
                parent.right = cur.left;
                return;
            }
            return;
        }

        //3.cur只有右子树
        if(cur.right != null && cur.left == null){

            //3.1 cur是根节点
            if(cur == root){
                root = cur.right;
                return;
            }

            //3.2 cur不是根节点，且cur是parent的左子树
            if(cur == parent.left){
                parent.left = cur.right;
                return;
            }

            //3.3 cur不是根节点，且cur是parent的右子树
            if(cur == parent.right){
                parent.right = cur.left;
                return;
            }
            return;
        }

        // 4.cur有两个子树
        if(cur.left != null && cur.right != null){
            //这时候就无需考虑cur是不是根节点的情况了，因为这里并没有真正删除cur指向的节点，即使cur是root.
            //也无需修改root的指向，因为实际找寻的是“替罪羊节点”
            //首先要找到右子树中的最小值，=> 替罪羊
            //后续删除替罪羊，同时把替罪羊的父节点记录一下

            //第一步，先找到替罪羊
            Node goat = cur.right;
            Node goatParent = cur;
            while(goat.left != null){
                goatParent = goat;
                goat = goat.left;
            }
            //这个while循环结束之后，goat指向的就是cur的右子树的最左侧节点

            //第二步，移花接木，把替罪羊的值，赋值到cur节点中
            cur.key = goat.key;

            //第三步，删除goat节点（goat是没有左子树的，让goatParent直接连上goat的右子树即可）
            //即使goat的右子树是空的，也不影响
            //这里还有一个坑，那就是没有触发while这段代码，那么goat就是goatParent的右子树
            goatParent.left = goat.right;
            if(goat == goatParent.left){
                goatParent.left = goat.right;
            }else{
                goatParent.right = goat.right;
            }
        }
    }



    public static void main(String[] args) {
        int [] arr = {1,3,6,2,5,0,8,10,9,7};

        BinarySearchTree tree = new BinarySearchTree();
        for(int key : arr){
            tree.insert(key);
        }
//        tree.print();
        System.out.println(tree.find(0));
    }

}
